package model;

import java.io.FileReader;
import java.io.IOException;
import java.util.Scanner;

/**
 * Camping (Tentje-Boompje) puzzle solver
 * 
 * @author Pieter Koopman (number?)
 * @author Karen Berntsen (s0815799)
 * @author Erik Stens (s0615374)
 */
public class Camping {
	private static int[][]	dTree	= new int[][] { { -1, 0 }, { 0, -1 }, { 0, 1 }, { 1, 0 } };
	private static int[][]	dTent	= new int[][] { { -1, -1 }, { 0, -1 }, { 1, -1 }, { -1, 0 }, { 1, 0 }, { -1, 1 }, { 0, 1 }, { 1, 1 } };
	
	private int				width, height;
	private FieldType[][]	camping;
	private boolean			foundSolution;
	private int[]			nTentsRow, nTentsColumn, currentNTentsRow, currentNTentsColumn;
	
	/**
	 * constructor reads camping from given file format: height width lines with 'b' or 'B' for TREE and anything else for empty + count (one digit) line with vertical counts (each count is one digit)
	 * 
	 * @param fileName
	 */
	public Camping(String fileName) throws IOException {
		FileReader file = new FileReader(fileName);
		Scanner scan = new Scanner(file);
		height = scan.nextInt();
		width = scan.nextInt();
		scan.nextLine();
		
		camping = new FieldType[width][height];
		nTentsColumn = new int[width];
		nTentsRow = new int[height];
		currentNTentsColumn = new int[width];
		currentNTentsRow = new int[height];
		
		for (int y = 0; y < height; y++) {
			String line = scan.nextLine().toLowerCase();
			if (line.length() <= width) {
				throw new IOException("line " + y + " is too short");
			}
			for (int x = 0; x < width; x++) {
				switch (line.charAt(x)) {
					case 'b':
						camping[x][y] = FieldType.TREE;
						break;
					default:
						camping[x][y] = FieldType.GRASS;
				}
			}
			nTentsRow[y] = Character.digit(line.charAt(width), 10);
		}
		String line = scan.nextLine();
		if (line.length() < width) {
			throw new IOException("last line is too short");
		}
		for (int x = 0; x < width; x++) {
			nTentsColumn[x] = Character.digit(line.charAt(x), 10);
		}
		file.close();
	}
	
	/**
	 * produces a multi-line string describing the Camping
	 * 
	 * @return the string
	 */
	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		for (int y = 0; y < height; y++) {
			for (int x = 0; x < width; x++) {
				sb.append(camping[x][y]);
			}
			sb.append(nTentsRow[y] + "\n");
		}
		for (int x = 0; x < width; x++) {
			sb.append(nTentsColumn[x] + " ");
		}
		sb.append("\n");
		return sb.toString();
	}
	
	/**
	 * checks if the coordinates are within the bounds of the camping
	 * 
	 * @param x
	 * @param y
	 * @return true if the coordinates are within bounds
	 */
	private boolean onCamping(int x, int y) {
		return 0 <= x && x < width && 0 <= y && y < height;
	}
	
	/**
	 * Generic function for checking for neighbours based on coordinate arrays that define the relative position of possible neighbours
	 * 
	 * @param x
	 * @param y
	 * @param fieldType
	 * @return whether there were neighbours
	 */
	private boolean nextTo(int x, int y, FieldType fieldType) {
		int[][] d;
		switch (fieldType) {
			case TREE:
				d = dTree;
				break;
			case TENT:
				d = dTent;
				break;
			default:
				throw new RuntimeException("Can't test the neighbours of type '" + fieldType + "'");
		}
		
		for (int[] dCoord : d) {
			int xCoord = x + dCoord[0];
			int yCoord = y + dCoord[1];
			if (onCamping(xCoord, yCoord)) {
				if (camping[xCoord][yCoord] == fieldType) {
					return true;
				}
			}
		}
		return false;
	}
	
	/**
	 * checks whether placing a tent on this coordinate is still valid based on the predefined amount of tents in that column and row
	 * 
	 * @param x
	 * @param y
	 * @return if a tent would fit on the camping at this coordinate
	 */
	private boolean fitsOnCamping(int x, int y) {
		return currentNTentsColumn[x] < nTentsColumn[x] && currentNTentsRow[y] < nTentsRow[y];
	}
	
	/**
	 * function that starts a recursive backtracking algorithm for placing tents on this camping
	 */
	public void placeTents() {
		placeTents(0);
	}
	
	private void placeTents(int i) {
		int y = i / width;
		int x = i % width;
		
		if (x == 0 && y != 0) {
			if (currentNTentsRow[y - 1] < nTentsRow[y - 1]) {
				return;
			}
		}
		
		if (i >= width * height) {
			foundSolution = true;
			System.out.println(this);
			return;
		}
		
		// System.out.println("tests for i = " + i + " - correctType: " + (camping[x][y] == FieldType.GRASS) + ", fits: " + fitsOnCamping(x, y) + ", nextToTree: " + nextTo(x, y, FieldType.TREE) + ", nextToTent: " + !nextTo(x, y,
		// FieldType.TENT));
		if (camping[x][y] == FieldType.GRASS && fitsOnCamping(x, y) && nextTo(x, y, FieldType.TREE) && !nextTo(x, y, FieldType.TENT)) {
			camping[x][y] = FieldType.TENT;
			currentNTentsColumn[x]++;
			currentNTentsRow[y]++;
			
			placeTents(i + 1);
			
			if (foundSolution) {
				return;
			}
			
			// backtracking
			camping[x][y] = FieldType.GRASS;
			currentNTentsColumn[x]--;
			currentNTentsRow[y]--;
		}
		
		placeTents(i + 1);
		
		return;
	}
}
